package io.gitee.wiqer.hard;

import io.gitee.wiqer.ListNode;

import java.util.ArrayList;

/**
 * 描述
 * 合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
 *
 * 数据范围：节点总数 0 \le n \le 50000≤n≤5000，每个节点的val满足 |val| <= 1000∣val∣<=1000
 * 要求：空间复杂度 O(1)O(1)（即额外使用常数大小的空间），时间复杂度 O(nlogn)O(nlogn)
 */
public class SolutionNC51_MergeKLists {
    /**
     * 分治
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ArrayList<ListNode> lists) {

        if (lists == null || lists.size() == 0) {
            return null;
        }

        ListNode headNode = null;

        for (int i = 0; i < lists.size(); i++) {
            headNode = connectListNode(headNode, lists.get(i));
        }

        return headNode;
    }

    public ListNode connectListNode (ListNode node1, ListNode node2) {

        if (node1 == null || node2 == null) {
            return node1 == null ? node2 : node1;
        }

        if (node1.val < node2.val) {
            node1.next = connectListNode(node1.next, node2);
            return node1;
        } else {
            node2.next = connectListNode(node1, node2.next);
            return node2;
        }
    }
}
